package primary.code07_Greedy;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author Yudi Wang
 * @date 2021/8/9 14:02
 * <p>
 * 给定启动资金 m, 限定可投资的项目数量 n, k 个可投资的项目（投资成本 cost, 投资净收益 profit）
 * 求解如何进行投资可以获取最大的收益
 */
public class Code05_Investment {

    static class Project {
        public int cost;
        public int profit;//默认收益均未正

        public Project(int cost, int profit) {
            this.cost = cost;
            this.profit = profit;
        }
    }

    /**
     * @param m        启动资金
     * @param n        可投资的项目数量
     * @param projects 可投资的项目
     * @return 总净收入
     */
    private static int maxProfit(int m, int n, List<Project> projects) {
        int res = 0;
        int times = 1;//进行第 times 次投资
        PriorityQueue<Project> minCose = new PriorityQueue<>(((o1, o2) -> o1.cost - o2.cost));
        PriorityQueue<Project> maxProfit = new PriorityQueue<>(((o1, o2) -> o2.profit - o1.profit));
        //初始化 成本小根堆
        for (Project project : projects) {
            minCose.add(project);
        }
        while (times <= n) {
            while (m >= minCose.peek().cost) {
                maxProfit.add(minCose.poll());
            }
            //无项目可投资，提前结束
            if (maxProfit.isEmpty()) {
                break;
            }
            //获取可投资的最大利润项目
            final Project maxProfitProject = maxProfit.poll();
            m += maxProfitProject.profit;
            res += maxProfitProject.profit;
            times++;
        }
        return res;
    }

    /**
     * 思路：
     * 按项目投资额初始化小根堆
     * 空的可投资项目利润大根堆
     * while 剩余投资次数
     * 从投资额小根堆弹出可投资的项目
     * 将可投资的项目放入利润大根堆
     * 如果，大根堆为空则提前返回，否则弹出利润大根堆作为本次投资项目
     * 投资利润更新
     * 利润大根堆清空放入投资额小根堆
     * end
     */
    private static int maxProfitTest(int m, int n, List<Project> projects) {
        PriorityQueue<Project> investmentMin = new PriorityQueue<>((p1, p2) -> p1.cost - p2.cost);
        PriorityQueue<Project> profitMax = new PriorityQueue<>((p1, p2) -> p2.profit - p1.profit);
        investmentMin.addAll(projects);
        int time = 1;
        int money = m;
        while (time <= n) {
            while (!investmentMin.isEmpty() && investmentMin.peek().cost <= money) {
                profitMax.add(investmentMin.poll());
            }
            if (profitMax.isEmpty()) return money - m;
            Project curProject = profitMax.poll();
            money += curProject.profit;
            investmentMin.addAll(profitMax);
            profitMax.clear();
            time++;
        }
        return money - m;
    }

    public static void main(String[] args) {
        List<Project> projects = new ArrayList<>();
        projects.add(new Project(1, 1));
        projects.add(new Project(1, 3));
        projects.add(new Project(2, 1));
        projects.add(new Project(4, 2));
        projects.add(new Project(5, 3));
        projects.add(new Project(8, 2));
        projects.add(new Project(10, 3));
        int maxProfit1 = maxProfit(1, 4, projects);
        int maxProfit2 = maxProfitTest(1, 4, projects);
        System.out.println("最大投资净收益：" + maxProfit1);
        System.out.println("最大投资净收益：" + maxProfit2);
    }
}
